﻿using System;
using System.Diagnostics;

namespace SfsTools.Core
{
    /// <summary>
    /// Keeps a list of free and used block regions.
    /// </summary>
    internal abstract class RegionMap : Object
    {
        #region Properties

        /// <summary>
        /// Contains the search hint. Used by <see cref="FindAndAllocate"/>.
        /// </summary>
        private int FIndexMapSearchHint;
        /// <summary>
        /// Contains the map of free and used blocks.
        /// </summary>
        private System.Collections.Generic.List<BlockRegionPair> FIndexMap = new System.Collections.Generic.List<BlockRegionPair>();
        /// <summary>
        /// Contains the list of index area entries that can be freely recycled.
        /// </summary>
        /// <remarks>Recycling is not implemented yet.</remarks>
        private readonly System.Collections.Generic.List<RecycleEntry> FRecycleEntries = new System.Collections.Generic.List<RecycleEntry>();

        #endregion

        #region Methods

        #region Allocate

        /// <summary>
        /// Invoked when no blocks could be allocated.
        /// </summary>
        /// <param name="count">The count of blocks requested.</param>
        /// <returns>The <see cref="BlockRegion"/> specifying the region allocated.</returns>
        [DebuggerStepThrough]
        protected abstract BlockRegion OnFull(long count);

        /// <summary>
        /// Allocates <paramref name="count"/> free blocks.
        /// </summary>
        /// <param name="count">The count of entries to allocate.</param>
        /// <returns>The index of the first block allocated.</returns>
        [DebuggerStepThrough]
        protected long FindAndAllocate(long count)
        {
            return FindAndAllocateRegion(count).Start;
        }

        /// <summary>
        /// Allocates <paramref name="count"/> free blocks.
        /// </summary>
        /// <param name="count">The count of entries to allocate.</param>
        /// <returns>The <see cref="BlockRegion"/> specifying the region allocated.</returns>
        protected BlockRegion FindAndAllocateRegion(long count)
        {
            for (int mapIdx = FIndexMapSearchHint; mapIdx < FIndexMap.Count; mapIdx++)
            {
                BlockRegionPair brp = FIndexMap[mapIdx];
                if (brp.A.Length > count)
                {
                    // Take it and split.
                    BlockRegionPair curr = new BlockRegionPair(
                        new BlockRegion(brp.A.Start, 0), new BlockRegion(brp.A.Start, count));
                    BlockRegionPair next = new BlockRegionPair(
                        new BlockRegion(brp.A.Start + count, brp.A.Length - count), new BlockRegion(brp.B.Start, brp.B.Length));
                    FIndexMap[mapIdx] = curr;
                    FIndexMap.Insert(mapIdx + 1, next);
                    // Perform merges.
                    MergeEntries(mapIdx);
                    return curr.B;
                }
                else if (brp.A.Length == count)
                {
                    // Take it, no split.
                    BlockRegionPair curr = new BlockRegionPair(new BlockRegion(brp.A.Start, 0),
                        new BlockRegion(brp.A.Start, brp.A.Length + brp.B.Length));
                    FIndexMap[mapIdx] = curr;
                    // Perform merges.
                    MergeEntries(mapIdx);
                    return brp.A;
                }
                else
                {
                    // Not enough free entries, continue.
                }
            }
            // Reached end of map, start from beginning.
            for (int mapIdx = 0; mapIdx < FIndexMapSearchHint; mapIdx++)
            {
                BlockRegionPair brp = FIndexMap[mapIdx];
                if (brp.A.Length > count)
                {
                    // Take it and split.
                    BlockRegionPair curr = new BlockRegionPair(
                        new BlockRegion(brp.A.Start, 0), new BlockRegion(brp.A.Start, count));
                    BlockRegionPair next = new BlockRegionPair(
                        new BlockRegion(brp.A.Start + count, brp.A.Length - count), new BlockRegion(brp.B.Start, brp.B.Length));
                    FIndexMap[mapIdx] = curr;
                    FIndexMap.Insert(mapIdx + 1, next);
                    // Merge entries.
                    MergeEntries(mapIdx);
                    return curr.B;
                }
                else if (brp.A.Length == count)
                {
                    // Take it, no split.
                    BlockRegionPair curr = new BlockRegionPair(new BlockRegion(brp.A.Start, 0),
                        new BlockRegion(brp.A.Start, brp.A.Length + brp.B.Length));
                    FIndexMap[mapIdx] = curr;
                    // Perform merges.
                    MergeEntries(mapIdx);
                    return brp.A;
                }
                else
                {
                    // Not enough free entries, continue.
                }
            }
            // Reached search hint -> no free entries.
            // Check if recycle list is empty.
            if (FRecycleEntries.Count > 0)
            {
                for (int i = 0; i < FRecycleEntries.Count; i++)
                {
                    RecycleEntry re = FRecycleEntries[i];
                    if (re.Region.Length >= count)
                    {
                        return RecycleEntries(i, count);
                    }
                }
            }
            // Recycle list is empty as well.
            return OnFull(count);
        }

        /// <summary>
        /// Attempts to allocate the specified region.
        /// </summary>
        /// <param name="region">The region to allocate.</param>
        /// <exception cref="InvalidAllocationException">The requested region could not be allocated.</exception>
        public void AllocateRegion(BlockRegion region)
        {
            int index;
            for (index = 0; index < FIndexMap.Count; index++)
            {
                if (region.Length == 0)
                {
                    // Nothing to allocate.
                    break;
                }
                if (FIndexMap[index].A.Contains(region))
                {
                    break;
                }
                else if (FIndexMap[index].B.Contains(region))
                {
                    // The region we are trying to allocate is already contained
                    // in an allocated region (=double allocation)
                    throw new InvalidAllocationException("region", 1);
                }
                else
                {
                    // Not in A, not in B, keep looking.
                }
            }
            if (index >= FIndexMap.Count)
            {
                // Either outside of the map, or intersects with an allocated region.
                throw new InvalidAllocationException("region", 2);
            }
            BlockRegionPair brp = FIndexMap[index];
            // Its in here... decide how to split A.
            if (brp.A.Start == region.Start)
            {
                if (brp.A.Length == region.Length)
                {
                    // Exact match.
                    FIndexMap[index] = new BlockRegionPair(
                        new BlockRegion(brp.A.Start, 0),
                        new BlockRegion(brp.A.Start, brp.A.Length + brp.B.Length));
                    //MergeEntries(index);
                }
                else if (brp.A.Length < region.Length)
                {
                    // Allocate A, and allocate some from the next region.
                    // This is not possible, as the RLE map is well formed, and
                    // the next region after A is used (unless its zero length,
                    // in which case it would have been merged into A).
                    throw new InvalidAllocationException("region", 3);
                }
                else
                {
                    // A is longer than we would like to allocate. Split it in two.
                    if (index < FIndexMap.Count - 1)
                    {
                        // Have next.
                        FIndexMap[index] = new BlockRegionPair(
                            new BlockRegion(region.Start, 0),
                            new BlockRegion(region.Start, region.Length));
                        BlockRegionPair brp2 = new BlockRegionPair(
                            new BlockRegion(region.Start + region.Length, brp.A.Length - region.Length),
                            new BlockRegion(brp.B.Start, brp.B.Length));
                        FIndexMap.Insert(index + 1, brp2);
                        // Merge potentially superfluous entries?
                        // The merge will never succeed, because in order to succeed,
                        // the next BRP has to be a 0-free region, which would already
                        // have been merged to this entry.
                        Debug.Assert(FIndexMap[index + 2].A.Length > 0);
                        //MergeEntries(index + 1);
                    }
                    else
                    {
                        // Create next.
                        FIndexMap[index] = new BlockRegionPair(
                            new BlockRegion(region.Start, 0),
                            new BlockRegion(region.Start, region.Length));
                        BlockRegionPair brp2 = new BlockRegionPair(
                            new BlockRegion(region.Start + region.Length, brp.A.Length - region.Length),
                            new BlockRegion(brp.B.Start, brp.B.Length));
                        FIndexMap.Add(brp2);
                    }
                }
            }
            else if (brp.A.Start < region.Start)
            {
                long delta = region.Start - brp.A.Start;
                // A portion of A will still be unallocated.
                if (region.Length + delta > brp.A.Length)
                {
                    // Allocate A, and allocate some from the next region.
                    // This is not possible, as the RLE map is well formed, and
                    // the next region after A is used (unless its zero length,
                    // in which case it would have been merged into A).
                    throw new InvalidAllocationException("region", 3);
                }
                else if (region.Length + delta == brp.A.Length)
                {
                    // Allocate second half of A. Merge the used portion with the next entry,
                    // create one if there isnt already.
                    FIndexMap[index] = new BlockRegionPair(
                        new BlockRegion(brp.A.Start, delta),
                        new BlockRegion(region.Start, brp.B.Length + region.Length));
                }
                else
                {
                    // Three-way split.
                    if (index < FIndexMap.Count - 1)
                    {
                        // Have next.
                        FIndexMap[index] = new BlockRegionPair(
                            new BlockRegion(brp.A.Start, delta),
                            new BlockRegion(region.Start, region.Length));
                        BlockRegionPair brp2 = new BlockRegionPair(
                            new BlockRegion(region.Start + region.Length, brp.A.Length - region.Length - delta),
                            new BlockRegion(brp.B.Start, brp.B.Length));
                        FIndexMap.Insert(index + 1, brp2);
                        // Merge potentially superfluous entries?
                        // The merge will never succeed, because in order to succeed,
                        // the next BRP has to be a 0-free region, which would already
                        // have been merged to this entry.
                        Debug.Assert(FIndexMap[index + 2].A.Length > 0);
                        //MergeEntries(index + 1);
                    }
                    else
                    {
                        // Create next.
                        FIndexMap[index] = new BlockRegionPair(
                            new BlockRegion(brp.A.Start, delta),
                            new BlockRegion(region.Start, region.Length));
                        BlockRegionPair brp2 = new BlockRegionPair(
                            new BlockRegion(region.Start + region.Length, brp.A.Length - region.Length - delta),
                            new BlockRegion(brp.B.Start, brp.B.Length));
                        FIndexMap.Add(brp2);
                    }
                }
            }
            else
            {
                // Not possible.
                Debug.Fail("Allocate: not possible");
                throw new InvalidOperationException();
            }
            MergeEntries(index);
        }

        #endregion

        #region Reserve region

        /// <summary>
        /// Reserves the specified region, taking preexisting allocations into account.
        /// </summary>
        /// <param name="region">The region to reserve.</param>
        public void ReserveRegion(BlockRegion region)
        {
            int index;
            for (index = 0; index < FIndexMap.Count; index++)
            {
                if (region.Length == 0)
                {
                    // Nothing to reserve.
                    break;
                }
                BlockRegionPair brp = FIndexMap[index];
                if (brp.B.Start + brp.B.Length <= region.Start)
                {
                    // Not overlapping.
                    continue;
                }
                // Is completely in A?
                if (brp.A.Contains(region))
                {
                    // Completely contained.
                    AllocateRegion(region);
                    return;
                }
                // Is completely in B?
                if (brp.B.Contains(region))
                {
                    // Already allocated.
                    break;
                }
                // Does A at least partially overlap the region?
                if (brp.A.Start + brp.A.Length > region.Start)
                {
                    long delta = region.Start - brp.A.Start;
                    // The region overlaps A. Mark the overlapping part of A as allocated.
                    FIndexMap[index] = new BlockRegionPair(
                        new BlockRegion(brp.A.Start, delta),
                        new BlockRegion(region.Start, brp.B.Length + brp.A.Length - delta));
                    // If region does not extend to the end of B, exit.
                    if (region.Start + region.Length < brp.B.Start + brp.B.Length)
                        break;
                    // Adjust requested region.
                    region = new BlockRegion(brp.B.Start + brp.B.Length,
                        region.Length - (brp.B.Start + brp.B.Length - region.Start));
                    if ((delta == 0) && (index > 0))
                    {
                        // prev has B, this has empty A and nonempty B. merge.
                        MergeEntries(index);
                        index--;
                    }
                }
                else if (brp.B.Start + brp.B.Length <= region.Start + region.Length)
                {
                    // B ends before the region ends. Adjust the requested region.
                    long delta = brp.B.Start + brp.B.Length - region.Start;
                    region = new BlockRegion(region.Start + delta, region.Length - delta);
                    MergeEntries(index);
                }
                else
                {
                    // The region ends before B ends.
                    break;
                }
            }
            if ((index >= FIndexMap.Count) && (region.Length > 0))
            {
                // Outside of the map.
                throw new InvalidAllocationException("region", 2);
            }
            // The work is done in the loop, all that remains is to merge all these allocated entries.
            MergeEntries(index);
        }

        #endregion

        #region Add to recycle list

        /// <summary>
        /// Adds an entry to the recycle list.
        /// </summary>
        /// <param name="entry">The entry.</param>
        [DebuggerStepThrough]
        protected void RegisterRecycleEntry(RecycleEntry entry)
        {
            FRecycleEntries.Add(entry);
        }

        #endregion

        #region Recycle entries

        /// <summary>
        /// Recycles an entry from the recycle list.
        /// </summary>
        /// <param name="index">The index into the recycle list.</param>
        /// <param name="count">The count of entries required.</param>
        /// <returns>The region of blocks recycled.</returns>
        private BlockRegion RecycleEntries(int index, long count)
        {
            RecycleEntry re = FRecycleEntries[index];
            BlockRegion br = re.Region;
            // Invoke callback.
            re.Recycle();
            if (br.Length > count)
            {
                BlockRegion over = new BlockRegion(index + count, br.Length - count);
                re = AfterRecycleSplit(re, over);
                FRecycleEntries[index] = re;
                // TODO: Insert these entries into the index area entry map.
                for (int i = 0; i < FIndexMap.Count; i++)
                {
                    BlockRegionPair brp = FIndexMap[i];
                    if (brp.A.Start + brp.A.Length < over.Start)
                        continue;
                }
                throw new NotImplementedException();
            }
            Debug.Assert(br.Length >= count);
            FRecycleEntries.RemoveAt(index);
            return br;
        }

        /// <summary>
        /// Invoked when a region is split after recycling <paramref name="entry"/>.
        /// </summary>
        /// <param name="entry">The entry that was recycled.</param>
        /// <param name="region">The new region that still waits to be recycled.</param>
        /// <returns>An entry representing <paramref name="region"/>.</returns>
        [DebuggerStepThrough]
        protected virtual RecycleEntry AfterRecycleSplit(RecycleEntry entry, BlockRegion region)
        {
            return new NullRecycleEntry(region);
        }

        #endregion

        #region Un-recycle entries

        /// <summary>
        /// Remove entries from the recycle list.
        /// </summary>
        /// <param name="region">The region of entries to remove.</param>
        [DebuggerStepThrough]
        public void UnRecycleEntries(BlockRegion region)
        {
            for (int i = 0; i < FRecycleEntries.Count; i++)
            {
                RecycleEntry re = FRecycleEntries[i];
                if (re.Region.Equals(region))
                {
                    FRecycleEntries.RemoveAt(i);
                    return;
                }
            }
            Debug.Fail(String.Format("Cannot find region {0} in recycle list", region));
        }

        #endregion

        #region Keep entry index map well-formed RLE

        /// <summary>
        /// Merges adjacent used/full entries in the index area entry map.
        /// </summary>
        /// <param name="index"></param>
        private void MergeEntries(int index)
        {
            // Check if previous entries are also used/full.
            for (; index > 0; index--)
            {
                BlockRegionPair prev = FIndexMap[index - 1];
                BlockRegionPair curr = FIndexMap[index - 0];
                if (prev.A.Length == 0 && curr.A.Length == 0)
                {
                    BlockRegionPair brp = new BlockRegionPair(
                        new BlockRegion(prev.A.Start, 0), new BlockRegion(prev.B.Start, prev.B.Length + curr.B.Length));
                    FIndexMap[index - 1] = brp;
                    FIndexMap.RemoveAt(index);
                }
                else if (prev.B.Length == 0 && curr.B.Length == 0)
                {
                    BlockRegionPair brp = new BlockRegionPair(
                        new BlockRegion(prev.A.Start, prev.A.Length + curr.A.Length), new BlockRegion(curr.B.Start, 0));
                    FIndexMap[index - 1] = brp;
                    FIndexMap.RemoveAt(index);
                }
                else if (prev.B.Length > 0 && curr.B.Length > 0 && curr.A.Length == 0)
                {
                    BlockRegionPair brp = new BlockRegionPair(
                        new BlockRegion(prev.A.Start, prev.A.Length), new BlockRegion(prev.B.Start, prev.B.Length + curr.B.Length));
                    FIndexMap[index - 1] = brp;
                    FIndexMap.RemoveAt(index);
                }
                else if (prev.A.Length > 0 && curr.A.Length > 0 && prev.B.Length == 0)
                {
                    BlockRegionPair brp = new BlockRegionPair(
                        new BlockRegion(prev.A.Start, prev.A.Length + curr.A.Length), new BlockRegion(curr.B.Start, curr.B.Length));
                    FIndexMap[index - 1] = brp;
                    FIndexMap.RemoveAt(index);
                }
                else
                {
                    break;
                }
            }
            // Check if subsequent entries are also used/full.
            for (; index < FIndexMap.Count - 1; )
            {
                BlockRegionPair next = FIndexMap[index + 1];
                BlockRegionPair curr = FIndexMap[index + 0];
                if (next.A.Length == 0 && curr.A.Length == 0)
                {
                    BlockRegionPair brp = new BlockRegionPair(
                        new BlockRegion(curr.A.Start, 0), new BlockRegion(curr.B.Start, curr.B.Length + next.B.Length));
                    FIndexMap[index + 1] = brp;
                    FIndexMap.RemoveAt(index);
                }
                else if (next.B.Length == 0 && curr.B.Length == 0)
                {
                    BlockRegionPair brp = new BlockRegionPair(
                        new BlockRegion(curr.A.Start, curr.A.Length + next.A.Length), new BlockRegion(next.B.Start, 0));
                    FIndexMap[index + 1] = brp;
                    FIndexMap.RemoveAt(index);
                }
                else if (next.B.Length > 0 && curr.B.Length > 0 && next.A.Length == 0)
                {
                    BlockRegionPair brp = new BlockRegionPair(
                        new BlockRegion(curr.A.Start, curr.A.Length), new BlockRegion(curr.B.Start, curr.B.Length + next.B.Length));
                    FIndexMap[index +1 ] = brp;
                    FIndexMap.RemoveAt(index);
                }
                else if (next.A.Length > 0 && curr.A.Length > 0 && curr.B.Length == 0)
                {
                    BlockRegionPair brp = new BlockRegionPair(
                        new BlockRegion(curr.A.Start, curr.A.Length + next.A.Length), new BlockRegion(next.B.Start, next.B.Length));
                    FIndexMap[index + 1] = brp;
                    FIndexMap.RemoveAt(index);
                }
                else
                {
                    break;
                }
            }
            FIndexMapSearchHint = index;
        }

        #endregion

        #region Deallocate

        /// <summary>
        /// Mark the blocks in <paramref name="region"/> as free.
        /// </summary>
        /// <param name="region">The region to deallocate.</param>        
        /// <exception cref="ArgumentException">The argument <paramref name="region"/> specifies an invalid, overlapping or not allocated region.</exception>
        public void DeallocateRegion(BlockRegion region)
        {
            int index;
            for (index = 0; index < FIndexMap.Count; index++)
            {
                if (FIndexMap[index].A.Contains(region))
                {
                    // The region we are trying to free is already contained
                    // in a free region (=double free)
                    throw new InvalidDeallocationException("region", 1);
                }
                else if (FIndexMap[index].B.Contains(region))
                {
                    break;
                }
                else
                {
                    // Not in A, not in B, keep looking.
                }
            }
            if (index >= FIndexMap.Count)
            {
                // Either outside of the map, or intersects with an unallocated region.
                throw new InvalidDeallocationException("region", 2);
            }
            BlockRegionPair brp = FIndexMap[index];
            // Its in here... decide how to split B.
            if (brp.B.Start == region.Start)
            {
                if (brp.B.Length == region.Length)
                {
                    // Exact match.
                    FIndexMap[index] = new BlockRegionPair(
                        new BlockRegion(brp.A.Start, brp.A.Length + brp.B.Length),
                        new BlockRegion(brp.A.Start + brp.A.Length + brp.B.Length, 0));
                    MergeEntries(index);
                }
                else if (brp.B.Length < region.Length)
                {
                    // Deallocate B, and deallocate some from the next region.
                    // This is not possible, as the RLE map is well formed, and
                    // the next region after B is free (unless its zero length,
                    // in which case it would have been merged into B).
                    throw new InvalidDeallocationException("region", 3);
                }
                else
                {
                    // B is longer than we would like to deallocate. Simply
                    // extend A and shrink B.
                    FIndexMap[index] = new BlockRegionPair(
                        new BlockRegion(brp.A.Start, brp.A.Length + region.Length),
                        new BlockRegion(brp.B.Start + region.Length, brp.B.Length - region.Length));
                }
            }
            else if (brp.B.Start < region.Start)
            {
                long delta = region.Start - brp.B.Start;
                // A portion of B will still be allocated.
                if (region.Length + delta > brp.B.Length)
                {
                    // Deallocate B, and deallocate some from the next region.
                    // This is not possible, as the RLE map is well formed, and
                    // the next region after B is free (unless its zero length,
                    // in which case it would have been merged into B).
                    throw new InvalidDeallocationException("region", 3);
                }
                else if (region.Length + delta == brp.B.Length)
                {
                    // Deallocate second half of B. Merge the free portion with the next entry,
                    // create one if there isnt already.
                    if (index < FIndexMap.Count - 1)
                    {
                        // Have next.
                        FIndexMap[index] = new BlockRegionPair(
                            new BlockRegion(brp.A.Start, brp.A.Length),
                            new BlockRegion(brp.B.Start, delta));
                        BlockRegionPair brp2 = FIndexMap[index + 1];
                        FIndexMap[index + 1] = new BlockRegionPair(
                            new BlockRegion(region.Start, region.Length + brp2.A.Length),
                            new BlockRegion(brp2.B.Start, brp2.B.Length));
                    }
                    else
                    {
                        // Create next.
                        FIndexMap[index] = new BlockRegionPair(
                            new BlockRegion(brp.A.Start, brp.A.Length),
                            new BlockRegion(brp.B.Start, delta));
                        BlockRegionPair brp2 = new BlockRegionPair(
                            new BlockRegion(region.Start, region.Length),
                            new BlockRegion(region.Start + region.Length, 0));
                        FIndexMap.Add(brp2);
                    }
                }
                else
                {
                    // Three-way split.
                    if (index < FIndexMap.Count - 1)
                    {
                        // Have next.
                        FIndexMap[index] = new BlockRegionPair(
                            new BlockRegion(brp.A.Start, brp.A.Length),
                            new BlockRegion(brp.B.Start, delta));
                        BlockRegionPair brp2 = new BlockRegionPair(
                            new BlockRegion(region.Start, region.Length),
                            new BlockRegion(region.Start + region.Length, brp.B.Length - region.Length - delta));
                        FIndexMap.Insert(index + 1, brp2);
                        // Merge potentially superfluous entries?
                        // The merge will never succeed, because in order to succeed,
                        // the next BRP has to be a 0-free region, which would already
                        // have been merged to this entry.
                        Debug.Assert(FIndexMap[index + 2].A.Length > 0);
                        //MergeEntries(index + 1);
                    }
                    else
                    {
                        // Create next.
                        FIndexMap[index] = new BlockRegionPair(
                            new BlockRegion(brp.A.Start, brp.A.Length),
                            new BlockRegion(brp.B.Start, delta));
                        BlockRegionPair brp2 = new BlockRegionPair(
                            new BlockRegion(region.Start, region.Length),
                            new BlockRegion(region.Start + region.Length, brp.B.Length - region.Length - delta));
                        FIndexMap.Add(brp2);
                    }
                }
            }
            else
            {
                // Not possible.
                Debug.Fail("Deallocate: not possible");
                throw new InvalidOperationException();
            }
        }

        #endregion

        #region Misc

        /// <summary>
        /// Sets the already normalized map.
        /// </summary>
        /// <param name="list">The list containing the free-used pairs.</param>
        /// <exception cref="ArgumentNullException">The argument <paramref name="list"/> is <see langword="null"/>.</exception>
        [DebuggerStepThrough]
        protected void SetMap(System.Collections.Generic.List<BlockRegionPair> list)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            FIndexMap = list;
        }

        /// <summary>
        /// For testing.
        /// </summary>
        /// <returns></returns>
        [DebuggerStepThrough]
        internal BlockRegionPair[] GetMap()
        {
            return FIndexMap.ToArray();
        }

        #endregion

        #endregion

        #region Constructors
        /// <overloads>Initializes a new instance of <see cref="RegionMap"/>.</overloads>
        /// <summary>
        /// Initializes a new instance of <see cref="RegionMap"/>.
        /// </summary>
        [DebuggerStepThrough]
        protected RegionMap()
            : base()
        {
        }
        #endregion

        #region Helper classes

        /// <summary>
        /// Contains a <see cref="BlockRegion"/> and a recycle callback.
        /// </summary>
        public abstract class RecycleEntry
        {
            #region Properties

            /// <summary>
            /// Gets the region that can be recycled.
            /// </summary>
            public readonly BlockRegion Region;

            #endregion

            #region Methods

            /// <summary>
            /// Returns a <see cref="String"/> that represents the current <see cref="RecycleEntry"/>.
            /// </summary>
            /// <returns>A <see cref="String"/> that represents the current <see cref="RecycleEntry"/>.</returns>
            [DebuggerStepThrough]
            public override String ToString()
            {
                return new System.Text.StringBuilder().
                    Append('{').Append(Region).Append('}').
                    ToString();
            }

            /// <summary>
            /// Invokes the callback.
            /// </summary>
            public abstract void Recycle();
            
            #endregion

            #region Constructors
            /// <overloads>Initializes a new instance of <see cref="RecycleEntry"/>.</overloads>
            /// <summary>
            /// Initializes a new instance of <see cref="RecycleEntry"/>.
            /// </summary>
            /// <param name="region">The block region to recycle.</param>
            [DebuggerStepThrough]
            protected RecycleEntry(BlockRegion region)
            {
                Region = region;
            }
            #endregion
        }

        /// <summary>
        /// Recycle entry with no callback.
        /// </summary>
        private class NullRecycleEntry : RecycleEntry
        {
            #region Methods

            /// <summary>
            /// Invokes the callback.
            /// </summary>
            [DebuggerStepThrough]
            public override void Recycle()
            {
            }
            
            #endregion

            #region Constructors
            /// <overloads>Initializes a new instance of <see cref="NullRecycleEntry"/>.</overloads>
            /// <summary>
            /// Initializes a new instance of <see cref="NullRecycleEntry"/>.
            /// </summary>
            /// <param name="region">The block region to recycle.</param>
            [DebuggerStepThrough]
            public NullRecycleEntry(BlockRegion region)
                : base(region)
            {
            }
            #endregion
        }

        #endregion
    }
}
